/**
 * 01背包，有主件有附件，附件必须在相应主件选择的前提下才能选择
 * 问最大收益是多少
 * 首先对每一组附件做一个01背包，得到一组(cost, w)
 * 然后再加上本组主件的值，得到一组(cost, w)，表示选择本组能够达到的代价与收益
 * 将所有组的数据求出来，再做一个分组背包即可，每组只能选一个值
 */
#include <bits/stdc++.h>
using namespace std;

using llt = long long;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vi = vector<int>;
using vll = vector<llt>;


template<typename T>
void input(vector<T>&v, int n){
    v.assign(n + 1, {});
    for(int i=1;i<=n;++i) cin >> v[i];
}

template<typename T>
istream & operator >> (istream & is, vector<T> & v){
    for(auto & i : v) is >> i;
    return is;
}

llt const INF = 0x1F2F3F4F5F6F7F8F;
llt const NINF = -INF;
llt const MOD = 998244353LL;

void chkmax(llt & a, llt b){
    if(b == NINF) return;
    if(a < b) a = b;
}

llt chkadd(llt a, llt b){
    if(NINF == a or NINF == b) return NINF;
    return a + b;
}

int MaxV, N;
map<int, pair<pii, vpii>> Map;
vector<vpii> Item;
vector<llt> D;

void work(){
    cin >> MaxV >> N;
    for(int v,w,q,i=1;i<=N;++i){ // 记录主件与附件
        cin >> v >> w >> q;
        if(q){
            auto it = Map.find(q);
            if(it == Map.end()) it = Map.insert(it, {q, {{0, 0}, vpii()}});
            it->second.second.emplace_back(v, v * w);
        }else{
            auto it = Map.find(i);
            if(it == Map.end()){
                it = Map.insert(it, {i, {{v, v * w}, vpii()}});
            }else{
                it->second.first = {v, v * w};
            }
        }
    }

#ifndef ONLINE_JUDGE
    for(const auto & p : Map){
        cout << p.first << ": ";
        cout << "(" << p.second.first.first << ", " << p.second.first.second << ")" << endl;
        cout << "    ";
        for(const auto & pp : p.second.second){
            cout << "(" << pp.first << ", " << pp.second << ")";
        }
        cout << endl;
    }
#endif    

    for(const auto & p : Map){
        D.assign(MaxV + 1, NINF);
        D[0] = 0;

        int maxv = MaxV - p.second.first.first;
        for(const auto & pp : p.second.second){ // 对附件做一个01背包
            for(int v=maxv;v>=pp.first;--v){
                chkmax(D[v], chkadd(D[v - pp.first], pp.second));
            }
        }

        Item.emplace_back(vpii());
        auto & vec = Item.back();
        for(int v=0;v<=maxv;++v){ // vec表示本组物品所能形成的所有可能的代价与收益 
            if(D[v] != NINF){
                vec.emplace_back(v + p.second.first.first, D[v] + p.second.first.second);
            }
        }
    }

#ifndef ONLINE_JUDGE
    for(const auto & vec : Item){
        for(const auto & pp : vec){
            cout << "(" << pp.first << ", " << pp.second << ")";
        }
        cout << endl;
    }
#endif

    D.assign(MaxV + 1, 0);
    for(const auto & vec : Item){ // 分组背包
        for(int v=MaxV;v>=0;--v){
            for(const auto & pp : vec){
                if(pp.first > v) continue;
                chkmax(D[v], chkadd(D[v - pp.first], pp.second));
            }  
        }
    }

    cout << D[MaxV] << endl;
    return;
}


int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int nofkase = 1;
    // cin >> nofkase; 
    while(nofkase--) work();    
    return 0;
}
